# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def isCompleteTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        queue = []
        nodes_count = 0
        last_pos = 0
        if root:
            queue.append((root, 1))
            nodes_count += 1
            last_pos = 1
        while queue:
            node, pos = queue.pop(0)
            if node:
                queue.append((node.left, 2 * pos))
                queue.append((node.right, 2 * pos + 1))
                nodes_count += 2
            last_pos = pos

        return last_pos == nodes_count
